package com.example.arithmeticleetcode.leetcode.dec;

/**
 * @program: arithmetic-leetcode
 * @description: 只针对8皇后进行进制优化
 * @author: FangZhen
 * @create: 2020-12-09 11:27
 **/
public class PlaceNQueens03 {

    public static void main(String[] args) {
        int n = 6;
        System.out.println(n % 2);
        System.out.println(n & 1);

        new PlaceNQueens03().placeNQueens();
    }

    int[] queens;


    /**
     * 标记某一列是否有皇后
     */
    byte cols;

    /**
     * 标记左对角线是否有皇后 k < 0 左上角->右下角
     */
    short leftTop;

    /**
     * 标记右对角线是否有皇后 右上角->左下角
     */
    short rightTop;


    /**
     * 多少种摆法
     */
    int ways;

    void placeNQueens() {

        queens = new int[8];
        place(0);
        System.out.println("8皇后，一共有" + ways + "种摆法！");
    }

    /**
     * 从第几行开始摆放皇后
     *
     * @param row
     */
    void place(int row) {

        if (row == 8) {
            show();
            ways++;
            return;
        }

        for (int col = 0; col < 8; col++) {

            //剪枝操作

            //在当前列上 应用 与 求这个列上是否有皇后
            int cv = 1 << col;
            if ((cols & cv) != 0) continue;
            //在当前对角线上
            int lv = 1 << (row - col + 7);
            if ((leftTop & lv) != 0) continue;
            int rv = 1 << (row + col);
            if ((rightTop & rv) != 0) continue;


            //在第row第col列摆放皇后
            queens[row] = col;
            //应用 或 进行变为1
            cols |= cv;
            leftTop |= lv;
            rightTop |= rv;
            place(row + 1);
            //先取反再进行 与 运算
            cols &= ~cv;
            leftTop &= ~lv;
            rightTop &= ~rv;

        }
    }


    void show() {
        for (int row = 0; row < 8; row++) {
            for (int col = 0; col < 8; col++) {
                if (queens[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("----------------------------------------");
    }
}
